package graphNew;


import java.awt.Dimension;
import java.awt.Paint;
import java.util.HashSet;
import java.util.Set;
import java.util.Vector;

import javax.swing.JFrame;

import main.Translating;

import org.apache.commons.collections15.Transformer;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import components.*;
import edu.uci.ics.jung.algorithms.layout.FRLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.visualization.VisualizationViewer;
import edu.uci.ics.jung.visualization.control.DefaultModalGraphMouse;
import edu.uci.ics.jung.visualization.control.ModalGraphMouse;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;
/**
 * @author dannysi
 *a graph which we gonna use the dinic algo on it
 * 
 */
public class DinicMainGraph {
	//GRAPH
	private DefaultDirectedWeightedGraph<Operator, FlowingEdge> maingraph;
	//source vertex
	private Operator source;
	//sink vertex
	private Operator sink;

	
	
	public DinicMainGraph(Vector<Goal> goals,MainGraph mg) throws Exception{
		
		maingraph=new DefaultDirectedWeightedGraph<Operator, FlowingEdge>(FlowingEdge.class);
		//adding vertexes
		for (Operator i:mg.getMainGraph().vertexSet()){
			maingraph.addVertex(i);
		}
		//adding edges
		for (DefaultWeightedEdge i:mg.getMainGraph().edgeSet()){
			FlowingEdge x=maingraph.addEdge(mg.getMainGraph().getEdgeSource(i),mg.getMainGraph().getEdgeTarget(i));
			x.setCapacity(maingraph.getEdgeWeight(x));
		}
		
		source=new Operator("source");
		sink=new Operator("sink");
		
		source.setSource(true);
		sink.setSink(true);		
		
		maingraph.addVertex(source);
		maingraph.addVertex(sink);
		
		for (Operator i:maingraph.vertexSet()){
			//edges from source
			if (i.confirm() && i!=source && i!=sink){
				FlowingEdge x=maingraph.addEdge(source,i);
				maingraph.setEdgeWeight(x, maingraph.getEdgeWeight(x));
				x.setCapacity(1);
			}
			//edges to sink
			if (i.confirm(goals) && i!=source){
				FlowingEdge x=maingraph.addEdge(i, sink);
				maingraph.setEdgeWeight(x, maingraph.getEdgeWeight(x));
				x.setCapacity(1);
			}
		}
		
		
		
		
	}
	
	
	public DinicMainGraph(
			DefaultDirectedWeightedGraph<Operator, FlowingEdge> g, Operator s,
			Operator t) {
		maingraph=g;
		source=s;
		sink=t;
		for (FlowingEdge i:maingraph.edgeSet())
			i.reset();
		
	}

	
	/**
	 * layered network 
	 * @param graph the graph 
	 * @param s the source vertex
	 * @return  a layered network
	 * @throws Exception if s is not in the graph
	 */
	
	
	public static DefaultDirectedWeightedGraph<Operator, FlowingEdge> getLayeredNetwork(DefaultDirectedWeightedGraph<Operator, FlowingEdge> graph,Operator s) throws Exception{
		//input check
		if (!graph.containsVertex(s))
			throw new Exception("source vertex not in the graph");
		//init var
			//our answer
		DefaultDirectedWeightedGraph<Operator, FlowingEdge> S=new DefaultDirectedWeightedGraph<Operator, FlowingEdge>(FlowingEdge.class);
			//out last layer
		HashSet<Operator> lastLayer=new HashSet<Operator>();
		boolean changed=true;
		lastLayer.add(s);
		S.addVertex(s);
		//main loop
		while (S.vertexSet().size()<graph.vertexSet().size() &&changed){
			changed=false;
			HashSet<Operator> nextLayer=new HashSet<Operator>();
			//add vertexes
			for (Operator i:lastLayer){
				for (FlowingEdge j:graph.outgoingEdgesOf(i)){
					Operator k=graph.getEdgeTarget(j);
					if (!S.vertexSet().contains(k)){
						S.addVertex(k);
						nextLayer.add(k);
						changed=true;
					}
				}
			}
			//add edges
			for (Operator i:lastLayer){
				for (Operator j:nextLayer)
					if (graph.containsEdge(i,j)){
						FlowingEdge k=S.addEdge(i,j);
						S.setEdgeWeight(k, graph.getEdgeWeight(graph.getEdge(i, j)));
						k.setCapacity(graph.getEdge(i, j).getCapacity());
					}
			}
			lastLayer=nextLayer;
		//	System.out.println(S.vertexSet().size());
			
		}
		return S;
	}
	
	
	/**
	 * gets a residual network
	 * @param graph
	 * @return
	 */
	public static DefaultDirectedWeightedGraph<Operator, FlowingEdge> getResidualNetwork(DefaultDirectedWeightedGraph<Operator, FlowingEdge> graph){
		DefaultDirectedWeightedGraph<Operator, FlowingEdge> g=new DefaultDirectedWeightedGraph<Operator, FlowingEdge>(FlowingEdge.class);
		//VERTEX ADD
		for (Operator i:graph.vertexSet())
			g.addVertex(i);
		//EDGE ADD
		for (FlowingEdge i:graph.edgeSet()){
			FlowingEdge j=g.getEdge(graph.getEdgeTarget(i), graph.getEdgeSource(i));
			//System.out.println(graph.getEdgeTarget(i)+" "+graph.getEdgeSource(i));
			//if (!g.containsEdge(graph.getEdgeTarget(i), graph.getEdgeSource(i))){
				
				if (j==null){
					if (i.getFlow()==0){
						FlowingEdge e=g.addEdge(graph.getEdgeSource(i),graph.getEdgeTarget(i));
						if (e!=null)
							e.setCapacity(i.getCapacity());
					}else if (i.getFlow()==i.getCapacity()){
						FlowingEdge e=g.addEdge(graph.getEdgeTarget(i),graph.getEdgeSource(i));
						e.setCapacity(i.getCapacity());
					}else {
						FlowingEdge e=g.addEdge(graph.getEdgeTarget(i),graph.getEdgeSource(i));
						e.setCapacity(i.getFlow());
						e=g.addEdge(graph.getEdgeSource(i),graph.getEdgeTarget(i));
						e.setCapacity(i.getCapacity()-i.getFlow());
					}
				}else{
					int iCapa=0;
					int jCapa=0;
					iCapa=(int)(i.getCapacity()-i.getFlow()+j.getFlow());
					jCapa=(int)(j.getCapacity()-j.getFlow()+i.getFlow());
					if (jCapa>0){
						FlowingEdge e=g.addEdge(graph.getEdgeTarget(i),graph.getEdgeSource(i));
						if (e!=null) e.setCapacity(jCapa);
					}
					if (iCapa>0){
						FlowingEdge e=g.addEdge(graph.getEdgeSource(i),graph.getEdgeTarget(i));
						if (e!=null) e.setCapacity(iCapa);
					}
				}
				
				
			//}
		}
		return g;
	}
	
	//GETTERS
	
	/**
	 * GETTER
	 */
	public DefaultDirectedWeightedGraph<Operator, FlowingEdge> getMaingraph() {
		return maingraph;
	}
	/**
	 * GETTER
	 * @return
	 */
	public Operator getSource() {
		return source;
	}
	/**
	 * GETTER
	 * @return
	 */
	public Operator getSink() {
		return sink;
	}

	/**
	 * 
	 * @param graph the graph WITHOUT CIRCLES IN IT!!!!
	 * @param s source vertex
	 * @param t target vertex
	 * @return path from s to t
	 */
	
	public static Vector<FlowingEdge> getPath(DefaultDirectedWeightedGraph<Operator, FlowingEdge> graph,Operator s,Operator t){
		return getPath(graph, s, t,new Vector<FlowingEdge>(),new HashSet<Operator>());
	}
	/**
	 * return a cut in graph from s to t
	 * @param graph
	 * @param s
	 * @param t
	 * @return
	 * @throws Exception if no cut was found
	 */
	public static HashSet<Operator> getCut(DefaultDirectedWeightedGraph<Operator, FlowingEdge> graph,Operator s,Operator t) throws Exception{
		HashSet<Operator> ans=new HashSet<Operator>();
		if (getPath(graph, s, t,new Vector<FlowingEdge>(),ans)==null)
			return ans;
		else throw new Exception ("no Cut");
	}
	/**
	 * get a path in graph from s to t
	 * @param graph
	 * @param s
	 * @param t
	 * @param ans
	 * @param black
	 * @return
	 */
	private static Vector<FlowingEdge> getPath(DefaultDirectedWeightedGraph<Operator, FlowingEdge> graph,Operator s,Operator t,Vector<FlowingEdge> ans,Set<Operator> black){
		Vector<FlowingEdge> rec;
		if (s==t) return new Vector<FlowingEdge>();
		for (FlowingEdge j:graph.outgoingEdgesOf(s)){
			if (j.getCapacity()>j.getFlow() && !black.contains(j)&& !ans.contains(j)){
				ans.add(j);
				rec=getPath(graph,graph.getEdgeTarget(j),t,ans,black);
				if (rec!=null) { 
					return ans;
				}
				ans.remove(j);
			}
		}
		black.add(s);
		return null;
	}
	
	/**
	 * 
	 * @param path
	 * @return the bottle neck of the path
	 */
	
	public static double getBottleN(Vector<FlowingEdge> path){
		double min=Double.MAX_VALUE;
		for (FlowingEdge i:path)
			if (min>i.getCapacity()-i.getFlow())
				min=i.getCapacity()-i.getFlow();
		return min;
	}
	
	
	/**
	 * flowing in the main graph path 
	 * @param path
	 * @param layeredNetwork
	 * @throws Exception
	 */
	public  void flow (Vector<FlowingEdge> path, DefaultDirectedWeightedGraph<Operator, FlowingEdge> layeredNetwork) throws Exception{
		double remain=getBottleN(path);
		//System.out.println(f+" "+path);
		for (FlowingEdge i:path){
			FlowingEdge j=maingraph.getEdge(maingraph.getEdgeSource(i),maingraph.getEdgeTarget(i));
			FlowingEdge k=maingraph.getEdge(maingraph.getEdgeTarget(i),maingraph.getEdgeSource(i));
			if (k!=null){
				if (k.getFlow()>=remain)
					k.setFlow(-remain);
				else if(k.getFlow()<remain){
					remain-=k.getFlow();
					k.setFlow(-k.getFlow());
					if (j!=null)
						j.setFlow(remain);
					if (j==null && remain>0)
						throw new Exception ("trying to flow into none existing edge");
				}
						
			}
			else
				j.setFlow(remain);
			i.setFlow(remain);
		}
		
		
	}
	
	/**
	 * the whole dinic algorithm
	 * @throws Exception
	 */
	public void dinicFlow() throws Exception{
		boolean changed=true;
		DefaultDirectedWeightedGraph<Operator, FlowingEdge> resNetwork=getResidualNetwork(maingraph);
		DefaultDirectedWeightedGraph<Operator, FlowingEdge> layeredNetwork=getLayeredNetwork(resNetwork, source);
		while (changed){
			changed=false;
			Vector<FlowingEdge>p=getPath(layeredNetwork, source, sink);
			while(p!=null){
				changed=true;
				flow(p,layeredNetwork);
				p=getPath(layeredNetwork, source, sink);
			}
			resNetwork=getResidualNetwork(maingraph);
			layeredNetwork=getLayeredNetwork(resNetwork, source);
		}
		
	}
	/**
	 * returns the mincut in the graph
	 * @param left returns to here the left side of the cut
	 * @param right returns to here the right side of the cut
	 * @param cut returns the cut
	 * @return the cut value
	 * @throws Exception
	 */
	public int minCut(DefaultDirectedWeightedGraph<Operator, FlowingEdge> left,DefaultDirectedWeightedGraph<Operator, FlowingEdge> right,DefaultDirectedWeightedGraph<Operator, FlowingEdge> cut) throws Exception{
		DefaultDirectedWeightedGraph<Operator, FlowingEdge> resNetwork=getResidualNetwork(maingraph);
		DefaultDirectedWeightedGraph<Operator, FlowingEdge> layeredNetwork=getLayeredNetwork(resNetwork, source);
		HashSet<Operator> rightV=new HashSet<Operator>();
		HashSet<Operator> leftV=new HashSet<Operator>();
		rightV.addAll(maingraph.vertexSet());
		leftV.addAll(getCut(layeredNetwork, source, sink));
		rightV.removeAll(leftV);
		int ans=0;
		
		for (Operator i:leftV)
			left.addVertex(i);
		for (Operator i:rightV)
			right.addVertex(i);
		
		for (FlowingEdge i:maingraph.edgeSet()){
			if (leftV.contains(maingraph.getEdgeSource(i)) && leftV.contains(maingraph.getEdgeTarget(i)))
				left.addEdge(maingraph.getEdgeSource(i), maingraph.getEdgeTarget(i),i);
			else if (rightV.contains(maingraph.getEdgeSource(i)) && rightV.contains(maingraph.getEdgeTarget(i)))
				right.addEdge(maingraph.getEdgeSource(i), maingraph.getEdgeTarget(i),i);
			else if (leftV.contains(maingraph.getEdgeSource(i)) && rightV.contains(maingraph.getEdgeTarget(i))){
				cut.addVertex(maingraph.getEdgeSource(i));
				cut.addVertex(maingraph.getEdgeTarget(i));
				cut.addEdge(maingraph.getEdgeSource(i), maingraph.getEdgeTarget(i),i);
				ans+=i.getFlow();
			}
				
		}
		return ans;
		
			
		
	
	}
/**
 * resets the graph 
 */
	public void reset() {
		for (FlowingEdge i:maingraph.edgeSet())
			i.reset();
	}
	/**
	 * GUI
	 * @return
	 */
	public JFrame printDinicGraph(){
		Graph jungGraph = Translating.dinicNetworkToJungGraph(this);
		
		// The Layout<V, E> is parameterized by the vertex and edge types
		Layout<Operator, DefaultWeightedEdge> layout = new FRLayout<Operator, DefaultWeightedEdge>(jungGraph);
		layout.setSize(new Dimension(500,500)); // sets the initial size of the space
		
		// The BasicVisualizationServer<V,E> is parameterized by the edge types
		VisualizationViewer<Operator,DefaultWeightedEdge> vv =
		new VisualizationViewer<Operator,DefaultWeightedEdge>(layout);
		vv.setPreferredSize(new Dimension(600,600)); //Sets the viewing area size
		
		//transformer design pattern for painting sink / source differently
		Transformer<Operator,Paint> vertexPaint = new Transformer<Operator,Paint>() {
			public Paint transform(Operator op) {
				return op.getPaintingColor();
			}
		};
		
		//Vertices and edges view editing
		vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint);
		vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Operator>());
		//vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<DefaultWeightedEdge>());
		vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);
		
		//iterative mouse for ZOOM IN/OUT
		DefaultModalGraphMouse<Operator,DefaultWeightedEdge> gm = 
			new DefaultModalGraphMouse<Operator,DefaultWeightedEdge>();
		gm.setMode(ModalGraphMouse.Mode.TRANSFORMING);
		vv.setGraphMouse(gm);
		
		//graphic output / visualization
		JFrame frame = new JFrame("Main Graph");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.getContentPane().add(vv);
		frame.pack();
		frame.setVisible(true);	
		return frame;
	}	
	
	

}
